package packet1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class course4 {
    public static void main(String[] args) {
//        System.out.println(checkIfPrerequisite(3,new int[][]{{1,2},{2,0}},new int[][]{{1,0}}));
        System.out.println(checkIfPrerequisite(5,new int[][]{{0,1},{1,2},{2,3},{3,4}},new int[][]{{0,4},{4,0},{1,3},{3,0}}));
    }
        public static List<Boolean> checkIfPrerequisite1(int numCourses, int[][] prerequisites, int[][] queries) {
            boolean result[] = new boolean[queries.length];
            List<List<Integer>>  list = new ArrayList<>();
            for(int i = 0; i < numCourses; i++)
                list.add(new ArrayList<>());
            for(int i = 0; i < prerequisites.length; i++) {
                if (!list.get(prerequisites[i][1]).contains(prerequisites[i][0])) {
                    list.get(prerequisites[i][1]).add(prerequisites[i][0]);
                }

            }
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < list.get(i).size(); j++) {
                    if(!list.get(i).containsAll(list.get(list.get(i).get(j))))
                        list.get(i).addAll(list.get(list.get(i).get(j)));
                }
            }
            for (int i = 0; i < queries.length; i++) {
                if(list.get(queries[i][1]).contains(queries[i][0]))
                    result[i] = true;
            }
            List<Boolean> re = new ArrayList<>();
            for(boolean i : result)
                re.add(i);
            return re;
        }



        /*
        floyd算法
         */
    public static List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] adj = new boolean[numCourses][numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            adj[prerequisites[i][1]][prerequisites[i][0]] = true;
        }
        for (int i = 0; i < numCourses; i++) {
            for (int j = 0; j < numCourses; j++) {
                for (int k = 0; k < numCourses; k++) {
                    adj[j][k] = adj[j][k] || (adj[j][i] && adj[i][k]);
                }
            }
        }
        List<Boolean> list = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            list.add(adj[queries[i][1]][queries[i][0]]);
        }
        return list;
    }
}
/*
5
[[0,1],[1,2],[2,3],[3,4]]
[[0,4],[4,0],[1,3],[3,0]]
 */